`
https://leetcode.cn/problems/path-sum-iii/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function (root, targetSum) {
  if (root === null) return 0
  const prefixMap = new Map()
  let pathSum = 0
  let count = 0

  const traverse = (root) => {
    if (root === null) return

    // 把当前的值累加到路径和
    pathSum += root.val
    // 查找所有路径上所有路径和为 pathSum - targetSum 的路径条数
    count += (prefixMap.get(pathSum - targetSum) || 0)
    // 将当前路径和记录进前缀和映射
    prefixMap.set(pathSum, (prefixMap.get(pathSum) || 0) + 1)

    traverse(root.left)
    traverse(root.right)

    // 去除前缀和映射中对应当前路径和的出现次数
    prefixMap.set(pathSum, (prefixMap.get(pathSum) - 1))
    // 从路径和中删去本结点的值
    pathSum -= root.val
  }

  // 给整条路径的情况使用
  prefixMap.set(0, 1)
  traverse(root)
  return count
};